SYLLABUS

UNIT-I

Tree: Header nodes, Threads, Binary search trees, Searching, Insertion and deletion in a Binary search tree, AVL search trees, Insertion and deletion in AVL search tree, m-way search tree, Searching, Insertion and deletion in an m-way search tree, B-trees, Searching, Insertion and deletion in a B-tree, B+tree, Huffman’s algorithm, General trees.

UNIT-II

Graphs: Warshall’s algorithm for shortest path, Dijkstra algorithm for shortest path, Operations on graphs, Traversal of graph, Topological sorting.

UNIT-III

Sorting: Internal & external sorting, Radix sort, Quick sort, Heap sort, Merge sort, Tournament sort.
Searching: Liner search, binary search, merging, Comparison of various sorting and searching algorithms on the basis of their complexity.

UNIT-IV

Files: Physical storage devices and their characteristics, Attributes of a file viz fields, records, Fixed and variable length records, Primiry and secondary keys, Classification of files, File operations, Comparison of various types of files.
File organization: Serial, Sequential, Indexed-sequential, Random-access/Direct, Inverted, Multilist file organization.
Hashing: Introduction, Hashing functions and Collision resolution methods .